{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 3: Improving the way neural networks learn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The cross-entropy cost function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introducing the cross-entropy cost function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_35813)): verify that $\\sigma'(z) = \\sigma(z) (1-\\sigma(z))$\n",
    "\n",
    "The definition of the sigmoid function is: $\\sigma(z) = \\frac{1}{1 + e^{-z}} = (1 + e^{-z})^{-1}$.\n",
    "\n",
    "The derivative of the denominator is $-e^{-z}$ and therefore we have $\\sigma'(z) = + e^{-z} (1 + e^{-z})^{-2} = \\frac{e^{-z}}{(1 + e^{-z})^2}$\n",
    "\n",
    "And $\\sigma(z)(1 - \\sigma(z)) = \\frac{1}{1 + e^{-z}} \\frac{1 + e^{-z} - 1}{1 + e^{-z}} = \\frac{e^{-z}}{(1 + e^{-z})^2}$\n",
    "\n",
    "And so we have $\\sigma'(z) = \\sigma(z) (1-\\sigma(z))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercises_824189)): the roles of $y$s and $a$s in the cross-entropy cost function\n",
    "\n",
    "The correct cross-entropy cost function is $-[y \\ln a + (1-y) \\ln (1-a)]$.\n",
    "\n",
    "The (incorrect) similar expression $-[a \\ln y + (1-a) \\ln (1-y)]$ isn't defined when $y = 0$ or $y = 1$, because $\\ln(x)$ isn't defined when $x = 0$.\n",
    "\n",
    "This is an issue because $y = 0$ or $y = 1$ can clearly happen, as $y$ is the correct output (if the expected answer is \"yes\", we would ideally like the network to output exactly 1; in this case we would have $y = 1$).\n",
    "\n",
    "In the right definition, we might think that the same problem would arise when $a = 0$ or $a = 1$. However, this never happens with the sigmoid activation function, because $a = \\sigma(z)$ and whatever the weighted input $z$ for a neuron, we will always have $0 < \\sigma(z) < 1$ by definition of $\\sigma$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3: show that the cross-entropy function is still a good cost function when $0 < y < 1$.\n",
    "\n",
    "Namely, we need to show that the cross-entropy cost function $C(a) = - (y \\ln a + (1 - y) \\ln (1 - a))$ is minimized when $a = y$.\n",
    "\n",
    "Let's differentiate $C$:\n",
    "\n",
    "$C'(a) = - \\frac y a + \\frac{1-y}{1-a}$.\n",
    "\n",
    "We look for a local extremum by solving $C'(a) = 0$:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        -\\frac{y}{a} + \\frac{1-y}{1-a} = 0 & \\iff \\frac{y}{a} = \\frac{1-y}{1-a} \\\\\n",
    "        & \\iff y - ay = a - ay \\\\\n",
    "        & \\iff a = y\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "We have a unique extremum in $a = y$. To determine whether it is a minimum or a maximum, we compute the second derivative:\n",
    "\n",
    "$C''(a) = \\frac{y}{a^2} + \\frac{1 - y}{(1 - a)^2}$.\n",
    "\n",
    "Since we have supposed $0 < y < 1$, and as always $0 < a < 1$, we have for all $0 < a < 1$: $C''(a) \\geq 0$ (the function is convex). Therefore, the function was minimized when $a = y$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 1 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problems_382219)): Many-layer multi-neuron networks\n",
    "\n",
    "For a single training example $x$, we have for the quadratic cost function:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial C}{\\partial w_{jk}^L} &= a_k^{L-1} \\delta_j^L \\qquad \\text{(BP4)} \\\\\n",
    "        &= a_k^{L-1} \\frac{\\partial C}{\\partial a_j^L} \\sigma'(z_j^L) \\qquad \\text{(BP1)}\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "The cost function for a single training example is $C = \\frac 1 2 \\sum_i (a_i^L - y_i)^2$, so we have $\\frac{\\partial C}{\\partial a_j^L} = a_j^L - y_j$. This gives us:\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial w^L_{jk}} = a^{L-1}_k  (a^L_j-y_j) \\sigma'(z^L_j)$$\n",
    "\n",
    "And taking all training examples into account,\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial w^L_{jk}} = \\frac{1}{n} \\sum\\limits_x a^{L-1}_k  (a^L_j-y_j) \\sigma'(z^L_j)$$\n",
    "\n",
    "Now with the cross-entropy cost function, let's first compute $\\delta^L$ for a single training example $x$: for all neurons $j$ in the $L$th layer,\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\delta_j^L &= \\frac{\\partial C}{\\partial a_j^L} \\sigma'(z_j^L) \\qquad \\text{(BP1)} \\\\\n",
    "        &= - \\left( \\frac{y_j}{a_j^L} - \\frac{1 - y_j}{1 - a_j^L} \\right) \\sigma'(z_j^L) \\\\\n",
    "        &= - \\left( \\frac{y_j}{\\sigma(z_j^L)} - \\frac{1 - y_j}{1 - \\sigma(z_j^L)} \\right) \\sigma(z_j^L) \\left( 1 - \\sigma(z_j^L) \\right) \\\\\n",
    "        &= - \\left( y_j (1 - \\sigma(z_j^L)) - (1 - y_j) \\sigma(z_j^L) \\right) \\\\\n",
    "        &= \\sigma(z_j^L) - y_j \\\\\n",
    "        &= a_j^L - y_j\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "And so $\\delta^L = a^L - y$.\n",
    "\n",
    "Let's incorporate it into our previous calculus.\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial C}{\\partial w_{jk}^L} &= a_k^{L-1} \\delta_j^L \\qquad \\text{(BP4)} \\\\\n",
    "        &= a_k^{L-1} (a_j^L - y_j)\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "And taking all training examples into account,\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial w^L_{jk}} = \\frac{1}{n} \\sum\\limits_x a^{L-1}_k  (a^L_j-y_j)$$\n",
    "\n",
    "For the biases, everything is the same except that instead of using BP4 ($\\frac{\\partial C}{\\partial w_{jk}^L} = a_k^{L-1} \\delta_j^L$), we use BP3 ($\\frac{\\partial C}{\\partial b_j^L} = \\delta_j^L$) and so we don't have the $a_k^{L-1}$ part."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 2: using the quadratic cost when we have linear neurons in the output layer\n",
    "\n",
    "We use the quadratic cost function and the activation function $f: x \\rightarrow x$ in the last layer. We have for a single training example $x$ and for all neurons $j$ in the $L$th layer:\n",
    "\n",
    "$$\\delta_j^L = \\frac{\\partial C}{\\partial a_j^L} f'(z_j^L) \\qquad \\text{(BP1)}$$\n",
    "\n",
    "The cost function for a single training example is $C = \\frac 1 2 \\sum_i (a_i^L - y_i)^2$, so we have $\\frac{\\partial C}{\\partial a_j^L} = a_j^L - y_j$. And $\\forall x \\in \\mathbb{R}, f'(x) = 1$.\n",
    "\n",
    "So $\\delta_j^L = a_j^L - y_j$. In vector form:\n",
    "\n",
    "$$\\delta^L = a^L - y$$\n",
    "\n",
    "Applying BP4 gives us, for a single training example:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial C}{\\partial w_{jk}^L} &= a_k^{L-1} \\delta_j^L \\qquad \\text{(BP4)} \\\\\n",
    "        &= a_k^{L-1} (a_j^L - y_j)\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "For the biases we apply BP3:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial C}{\\partial b_j^L} &= \\delta_j^L \\qquad \\text{(BP3)} \\\\\n",
    "        &= (a_j^L - y_j)\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "And taking all training examples into account:\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial w^L_{jk}} = \\frac{1}{n} \\sum_x a^{L-1}_k  (a^L_j-y_j)$$\n",
    "\n",
    "And\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial b^L_{j}} = \\frac{1}{n} \\sum_x (a^L_j-y_j)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using the cross-entropy to classify MNIST digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What does the cross-entropy mean? Where does it come from?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 3 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problem_507295)): why it's not possible to eliminate the $x_j$ term through a clever choice of cost function\n",
    "\n",
    "The derivation of equation (61) began like this, using the chain rule:\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial w_j} = \\frac{\\partial C}{\\partial a} \\frac{\\partial a}{\\partial w_j}$$\n",
    "\n",
    "Since $a = \\sigma(\\sum_i w_i x_i + b)$, we have $\\frac{\\partial a}{\\partial w_j} = x_j \\sigma'(\\sum_i w_i x_i + b) = x_j \\sigma'(z)$.\n",
    "\n",
    "Using the cross-entropy cost function, we have managed to make $\\frac{\\partial C}{\\partial a}$ look like $\\frac{something}{\\sigma'(z)}$, eliminating the $\\sigma'(z)$ term in $\\frac{\\partial C}{\\partial w_j}$.\n",
    "\n",
    "Now we would like to make it look like $\\frac{something}{x_j}$. The problem is that whatever the choice of the cost function $C$, it can only depend on the network output $a$ (and the expected output $y$). Therefore, the contributions of each $x_j$ to the final activation $a$ can't be taken into account by $C$ (keeping in mind that an infinity of choices for the $\\{x_j\\}$ lead to the same weighted input $z$ and the same output $a$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Softmax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_332838)): construct an example showing that with a sigmoid output layer, the output activations won't always sum to 1\n",
    "\n",
    "Consider a 2-layer network made of a single input neuron and a single output neuron, with a weight $w$ (a scalar) and bias $b$. Its input (given by the input neuron) is $x$.\n",
    "\n",
    "Now whatever the input $x$, the weighted input will be $z = wx + b$ and the output $a = \\sigma(z) < 1$ since $\\forall x \\in \\mathbb{R}, \\sigma(x) < 1$. So the sum of the output activations, being equal to our unique output activation, won't be 1 (we can also construct examples where the sum of the output activations is more than 1).\n",
    "\n",
    "By contrast, had we used the softmax output layer in this case, we would have had:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\sum_j a_j &= \\frac{\\sum_j e^{z_j}}{\\sum_k e^{z_k}} \\\\\n",
    "        &= \\frac{e^z}{e^z} \\\\\n",
    "        &= 1\n",
    "    \\end{aligned}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercises_193619)): monotonicity of softmax\n",
    "\n",
    "For easier differentiation, let's reformulate $a_j^L$:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        a_j^L &= \\frac{e^{z_j^L}}{e^{z_j^L} + \\sum\\limits_{k \\neq j} e^{z_k^L}} \\\\\n",
    "        &= \\frac{1}{1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L}} \\\\\n",
    "        &= \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) ^{-1}\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "Now\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial a_j^L}{\\partial z_j^L} &= - \\frac{\\partial \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right)}{\\partial z_j^L} \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) ^{-2} \\\\\n",
    "        &= \\left( e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) ^{-2} \\\\\n",
    "        &= \\left( e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) \\left( a_j^L \\right) ^2 \\\\\n",
    "        &> 0\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "And for $k \\neq j$,\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial a_j^L}{\\partial z_k^L} &= - \\frac{\\partial \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right)}{\\partial z_k^L} \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) ^{-2} \\\\\n",
    "        &= - \\left( e^{-z_j^L} e^{z_k^L} \\right) \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) ^{-2} \\\\\n",
    "        &= - \\left( e^{-z_j^L} e^{z_k^L} \\right) \\left( a_j^L \\right) ^2 \\\\\n",
    "        &< 0\n",
    "    \\end{aligned}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6: non-locality of softmax\n",
    "\n",
    "We just showed that for $k \\neq j$, $\\frac{\\partial a_j^L}{\\partial z_k^L} \\neq 0$. This shows that $a_j^L$ depends on all weighted inputs $z_k^L$, not just $z_j^L$.\n",
    "\n",
    "But the previous derivation wasn't actually necessary to see that. Recall that with a softmax output layer, $a_j^L = \\frac{e^{z_j^L}}{\\sum_k e^{z_k^L}}$. Because of the sum in the denominator, we see directly that changing the value of any $z_k^L$ will change the value of $a_j^L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 4 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problem_905066)): Inverting the softmax layer\n",
    "\n",
    "By definition:\n",
    "\n",
    "$$a_j^L = \\frac{e^{z_j^L}}{\\sum_k e^{z_k^L}}$$\n",
    "\n",
    "So:\n",
    "\n",
    "$$z_j^L = \\ln \\left( a_j^L \\right) + \\ln \\left( \\sum_k e^{z_k^L} \\right)$$\n",
    "\n",
    "We just have to call $C$ the constant $\\ln \\left( \\sum_k e^{z_k^L} \\right)$, which is independent of $j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 5 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problems_919607)): derive equations (81) and (82)\n",
    "\n",
    "Let's first derive equation (81): $\\frac{\\partial C}{\\partial b_j^L} = a_j^L - y_j$.\n",
    "\n",
    "For clarity, let's call $y$ the expected output vector, made only of $0$s and $1$s, and $\\tilde{y}$ the integer such that $y_\\tilde{y} = 1$ (in the MNIST example, the correct digit).\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial C}{\\partial b_j^L} &= \\delta_j^L \\qquad \\text{(BP3)} \\\\\n",
    "        &= \\frac{\\partial C}{\\partial z_j^L} \\qquad \\text{by definition of } \\delta_j^L \\\\\n",
    "        &= \\sum\\limits_k \\frac{\\partial C}{\\partial a_k^L} \\frac{\\partial a_k^L}{\\partial z_j^L} \\qquad \\text{(chain rule)} \\\\\n",
    "        &= \\frac{\\partial C}{\\partial a_\\tilde{y}^L} \\frac{\\partial a_\\tilde{y}^L}{\\partial z_j^L} \\qquad \\text{as } C \\text{ only depends on } a_\\tilde{y}^L \\\\\n",
    "        &= - \\frac{1}{a_\\tilde{y}^L} \\frac{\\partial a_\\tilde{y}^L}{\\partial z_j^L} \\qquad \\text{as } C = - \\ln a_\\tilde{y}^L\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "At this point, we must treat 2 cases separately, using the expressions derived in Exercise 5.\n",
    "\n",
    "* If $j = \\tilde{y}$:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial C}{\\partial b_j^L} &= - \\frac{1}{a_j^L} \\left( e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) \\left( a_j^L \\right) ^2 \\qquad \\text{using the first expression from Exercise 5} \\\\\n",
    "        &= - a_j^L \\left( 1 +  e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} - 1 \\right) \\\\\n",
    "        &= - a_j^L \\left( \\frac{1}{a_j^L} - 1 \\right) \\qquad \\text{recalling from Exercise 5 that } a_j^L = \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) ^{-1} \\\\\n",
    "        &= a_j^L - 1 \\\\\n",
    "        &= a_j^L - y_j \\qquad \\text{since } y_j = y_\\tilde{y} = 1\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "* If $j \\neq \\tilde{y}$:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{\\partial C}{\\partial b_j^L} &= - \\frac{1}{a_\\tilde{y}^L} \\left(- e^{-z_\\tilde{y}^L} e^{z_j^L} \\right) \\left( a_\\tilde{y}^L \\right) ^2 \\qquad \\text{using the second expression from Exercise 5} \\\\\n",
    "        &= a_\\tilde{y}^L e^{-z_\\tilde{y}^L} e^{z_j^L} \\\\\n",
    "        &= \\frac{e^{z_\\tilde{y}^L}}{\\sum_k e^{z_k^L}} e^{-z_\\tilde{y}^L} e^{z_j^L} \\qquad \\text{by definition of } a_\\tilde{y}^L \\\\\n",
    "        &= \\frac{e^{z_j^L}}{\\sum_k e^{z_k^L}} \\\\\n",
    "        &= a_j^L \\\\\n",
    "        &= a_j^L - y_j \\qquad \\text{since } j \\neq \\tilde{y} \\text{ and so } y_j = 0\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "We have proven Equation (81): $\\frac{\\partial C}{\\partial b_j^L} = a_j^L - y_j$.\n",
    "\n",
    "The proof for equation (82) is exactly the same, except that instead of starting with $\\frac{\\partial C}{\\partial b_j^L} = \\delta_j^L$ using BP3, it starts with $\\frac{\\partial C}{\\partial w_{jk}^L} = a_k^{L-1} \\delta_j^L$ using BP4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 6: explanation of the \"softmax\" name\n",
    "\n",
    "Let's consider $a^L_j = \\frac{e^{c z^L_j}}{\\sum_k e^{c z^L_k}}$ with $c > 0$.\n",
    "\n",
    "* We still have $a_j^L \\geq 0$ for all $j$\n",
    "* The sum of the outputs of all neurons is still 1: $\\sum\\limits_j a_j^L = \\frac{\\sum\\limits_j e^{c z^L_j}}{\\sum\\limits_k e^{c z^L_k}} = 1$.\n",
    "\n",
    "Therefore, the output activations still form a probability distribution.\n",
    "\n",
    "What about the limit as $c \\rightarrow + \\infty$?\n",
    "\n",
    "Let's write the expression slightly differently:\n",
    "\n",
    "$$a_j^L = \\frac{1}{1 + e^{-c z_j^L} \\sum\\limits_{k \\neq j} e^{c z_k^L}} = \\frac{1}{1 + \\sum\\limits_{k \\neq j} e^{c( z_k^L - z_j^L)}}$$\n",
    "\n",
    "* If $z_j^L$ is not the maximum weighted input (there exists $m$ such that $z_m^L > z_j^L$), then we will have:\n",
    "\n",
    "$$\\lim_{c \\to + \\infty} e^{c(z_m^L - z_j^L)} = + \\infty $$\n",
    "\n",
    "And since all other terms in the sum are positive:\n",
    "\n",
    "$$\\lim_{c \\to + \\infty} \\sum\\limits_{k \\neq j} e^{c(z_k^L - z_j^L)} = + \\infty $$\n",
    "\n",
    "And therefore:\n",
    "\n",
    "$$\\lim_{c \\to + \\infty} a_j^L = 0$$\n",
    "\n",
    "* If $z_j^L$ is one of the $n \\geq 1$ maximal weighted inputs, we will have:\n",
    "  * for $k$ such that $z_k^L$ is another maximal weighted input, $\\lim_{c \\to + \\infty} e^{c(z_k^L - z_j^L)} = 1$ since $z_k^L - z_j^L = 0$;\n",
    "  * for $k$ such that $z_k^L$ is not one of the maximal weighted inputs, $\\lim_{c \\to + \\infty} e^{c(z_k^L - z_j^L)} = 0$ since $z_k^L - z_j^L < 0$;\n",
    "\n",
    "Therefore,\n",
    "\n",
    "$$\\lim_{c \\to + \\infty} \\sum\\limits_{k \\neq j} e^{c(z_k^L - z_j^L)} = n - 1$$\n",
    "\n",
    "And:\n",
    "\n",
    "$$\\lim_{c \\to + \\infty} a_j^L = \\frac 1 n$$\n",
    "\n",
    "(in particular, $\\lim_{c \\to + \\infty} a_j^L = 1$ if $z_j^L$ is the unique maximum).\n",
    "\n",
    "More succinctly,\n",
    "\n",
    "\\begin{eqnarray}\n",
    "   \\lim_{c \\to + \\infty} a_j^L = \\left\\{ \n",
    "    \\begin{array}{ll} \n",
    "      0 & \\mbox{if } z_j^L \\mbox{ is not a maximum weighted input} \\\\\n",
    "      \\frac 1 n & \\mbox{if } z_j^L \\mbox{ is one of } n \\mbox{ maximal weighted inputs}\n",
    "    \\end{array}\n",
    "  \\right.\n",
    "\\end{eqnarray}\n",
    "\n",
    "Now we see that when $c = 1$, we still put more weight on the bigger values because of the exponential function, but we take all of them into account, not just the maximal ones, hence the \"softmax\" name."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 7: Backpropagation with softmax and the log-likelihood cost\n",
    "\n",
    "We need to prove that $\\delta_j^L = a_j^L - y_j$. We've actually already done it in Problem 5, but I'll copy the relevant part here:\n",
    "\n",
    "For clarity, let's call $y$ the expected output vector, made only of $0$s and $1$s, and $\\tilde{y}$ the integer such that $y_\\tilde{y} = 1$ (in the MNIST example, the correct digit).\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\delta_j^L &= \\frac{\\partial C}{\\partial z_j^L} \\qquad \\text{by definition} \\\\\n",
    "        &= \\sum\\limits_k \\frac{\\partial C}{\\partial a_k^L} \\frac{\\partial a_k^L}{\\partial z_j^L} \\qquad \\text{(chain rule)} \\\\\n",
    "        &= \\frac{\\partial C}{\\partial a_\\tilde{y}^L} \\frac{\\partial a_\\tilde{y}^L}{\\partial z_j^L} \\qquad \\text{as } C \\text{ only depends on } a_\\tilde{y}^L \\\\\n",
    "        &= - \\frac{1}{a_\\tilde{y}^L} \\frac{\\partial a_\\tilde{y}^L}{\\partial z_j^L} \\qquad \\text{as } C = - \\ln a_\\tilde{y}^L\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "At this point, we must treat 2 cases separately, using the expressions derived in Exercise 5.\n",
    "\n",
    "* If $j = \\tilde{y}$:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\delta_j^L &= - \\frac{1}{a_j^L} \\left( e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) \\left( a_j^L \\right) ^2 \\qquad \\text{using the first expression from Exercise 5} \\\\\n",
    "        &= - a_j^L \\left( 1 +  e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} - 1 \\right) \\\\\n",
    "        &= - a_j^L \\left( \\frac{1}{a_j^L} - 1 \\right) \\qquad \\text{recalling from Exercise 5 that } a_j^L = \\left( 1 + e^{-z_j^L} \\sum\\limits_{k \\neq j} e^{z_k^L} \\right) ^{-1} \\\\\n",
    "        &= a_j^L - 1 \\\\\n",
    "        &= a_j^L - y_j \\qquad \\text{since } y_j = y_\\tilde{y} = 1\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "* If $j \\neq \\tilde{y}$:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\delta_j^L &= - \\frac{1}{a_\\tilde{y}^L} \\left(- e^{-z_\\tilde{y}^L} e^{z_j^L} \\right) \\left( a_\\tilde{y}^L \\right) ^2 \\qquad \\text{using the second expression from Exercise 5} \\\\\n",
    "        &= a_\\tilde{y}^L e^{-z_\\tilde{y}^L} e^{z_j^L} \\\\\n",
    "        &= \\frac{e^{z_\\tilde{y}^L}}{\\sum_k e^{z_k^L}} e^{-z_\\tilde{y}^L} e^{z_j^L} \\qquad \\text{by definition of } a_\\tilde{y}^L \\\\\n",
    "        &= \\frac{e^{z_j^L}}{\\sum_k e^{z_k^L}} \\\\\n",
    "        &= a_j^L \\\\\n",
    "        &= a_j^L - y_j \\qquad \\text{since } j \\neq \\tilde{y} \\text{ and so } y_j = 0\n",
    "    \\end{aligned}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overfitting and regularization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regularization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why does regularization help reduce overfitting?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other techniques for regularization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_195778)): why can't we use arbitrarily large rotations of training images?\n",
    "\n",
    "Because a $6$ is a $9$ rotated 180 degrees."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 8 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problem_455958)) (research problem): asymptotic performance of different machine learning algorithms\n",
    "\n",
    "I did not find a solution to this problem :("
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Weight initialization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 8 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_319349)): standard deviation of the weighted input\n",
    "\n",
    "Let's call $J = \\{ j \\mid x_j = 1 \\}$ the set of non null inputs. Its cardinal is supposed to be $\\frac{n_{in}}{2}$, or in this case $500$.\n",
    "\n",
    "The variance of $z$ is:\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        V(z) &= \\sum\\limits_{z \\in J} V(w_j) + V(b) \\\\\n",
    "        &= \\sum\\limits_{z \\in J} \\frac{1}{n_{in}} + 1 \\\\\n",
    "        &= \\frac{n_{in}}{2} \\frac{1}{n_{in}} + 1 \\\\\n",
    "        &= \\frac 3 2\n",
    "    \\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "So the standard deviation of $z$ is:\n",
    "\n",
    "$$s(z) = \\sqrt{\\frac 3 2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 9 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problem_735589)): Connecting regularization and the improved method of weight initialization\n",
    "\n",
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Handwriting recognition revisited: the code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 10 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problems_201277)): implement L1 regularization\n",
    "\n",
    "The code is in the `chap3p10` directory.\n",
    "\n",
    "First, we execute `exec_normal.py` which uses L2 regularization to make sure we get the same results as Nielsen:\n",
    "\n",
    "```\n",
    "Epoch 0 training complete\n",
    "Accuracy on evaluation data: 9418 / 10000\n",
    "Epoch 1 training complete\n",
    "Accuracy on evaluation data: 9535 / 10000\n",
    "Epoch 2 training complete\n",
    "Accuracy on evaluation data: 9566 / 10000\n",
    "...\n",
    "Epoch 27 training complete\n",
    "Accuracy on evaluation data: 9615 / 10000\n",
    "Epoch 28 training complete\n",
    "Accuracy on evaluation data: 9621 / 10000\n",
    "Epoch 29 training complete\n",
    "Accuracy on evaluation data: 9570 / 10000\n",
    "```\n",
    "\n",
    "Our best classification accuracy happens after Epoch 20, with a 96.39 percent accuracy. Nielsen had obtained 96.49 percent. Everything seems to be fine.\n",
    "\n",
    "Because we'll have to compare our L1 regularization with running unregularized, let's run unregularized by executing `exec_unregularized.py` (which is the same as `exec_normal.py` except that is sets `lmbda=0.0` instead of `lmbda=5.0`). For the remaining of this problem, we'll compare best-in-three-runs results. The classification accuracies indicated are the best ones obtained during the first 30 epochs of learning.\n",
    "\n",
    "**Unregularized**:\n",
    "\n",
    "* Run 1: 96.26 percent\n",
    "* Run 2: 96.32 percent\n",
    "* Run 3: 95.89 percent\n",
    "* Best-in-three: 96.32 percent\n",
    "* Average: 96.16 percent\n",
    "\n",
    "Now let's implement L1 regularization. In `chap3p10/network2_L1.py`, the only change I made is replacing:\n",
    "\n",
    "```\n",
    "self.weights = [(1-eta*(lmbda/n))*w-(eta/len(mini_batch))*nw\n",
    "                for w, nw in zip(self.weights, nabla_w)]\n",
    "```\n",
    "\n",
    "With:\n",
    "\n",
    "```\n",
    "self.weights = [w-eta*(lmbda/n)*np.sign(w)-(eta/len(mini_batch))*nw\n",
    "                for w, nw in zip(self.weights, nabla_w)]\n",
    "```\n",
    "\n",
    "I tested the following values:\n",
    "\n",
    "**L1, $\\lambda = 5.0$**:\n",
    "\n",
    "* Run 1: 96.34 percent\n",
    "* Run 2: 96.10 percent\n",
    "* Run 3: 96.05 percent\n",
    "* Best-in-three: 96.34 percent\n",
    "* Average: 96.16 percent\n",
    "\n",
    "**L1, $\\lambda = 1.0$**:\n",
    "\n",
    "* Run 1: 96.66 percent\n",
    "* Run 2: 96.60 percent\n",
    "* Run 3: 96.09 percent\n",
    "* Best-in-three: 96.66 percent\n",
    "* Average: 96.45\n",
    "\n",
    "**L1, $\\lambda = 0.5$**:\n",
    "\n",
    "* Run 1: 96.48 percent\n",
    "* Run 2: 96.54 percent\n",
    "* Run 3: 96.23 percent\n",
    "* Best-in-three: 96.54 percent\n",
    "* Average: 96.42 percent\n",
    "\n",
    "**L1, $\\lambda = 0.2$**:\n",
    "\n",
    "* Run 1: 96.25 percent\n",
    "* Run 2: 96.31 percent\n",
    "* Run 3: 96.04 percent\n",
    "* Best-in-three: 96.31 percent\n",
    "* Average: 96.2 percent\n",
    "\n",
    "L1 regularization outperforms the absence of regularization for the best-in-three or average classification accuracy with each of these values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 11: `Network.cost_derivative` for the cross-entropy cost\n",
    "\n",
    "This is `Network.cost_derivative` in `network.py`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cost_derivative(self, output_activations, y):\n",
    "    \"\"\"Return the vector of partial derivatives \\partial C_x /\n",
    "    \\partial a for the output activations.\"\"\"\n",
    "    return (output_activations-y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which is then used in the line:\n",
    "\n",
    "```\n",
    "delta = self.cost_derivative(activations[-1], y) * \\\n",
    "    sigmoid_prime(zs[-1])\n",
    "```\n",
    "\n",
    "The previous lines correspond to BP1: $\\delta^L_j = \\frac{\\partial C}{\\partial a^L_j} \\sigma'(z^L_j)$, or rather $\\delta^L = \\nabla_a C \\odot \\sigma'(z^L)$. With (for a single training example) $C(a, y) = \\frac 1 2 \\sum\\limits_j \\left( a_j^L - y_j \\right) ^2$, we indeed have $\\frac{\\partial C}{\\partial a_j^L} = (a_j^L - y_j)$ and so $\\nabla_a C = (a - y)$.\n",
    "\n",
    "For the cross-entropy cost $C = - \\sum\\limits_j y_j \\ln(a_j^L) + (1 - y_j) \\ln(1 - a_j^L)$, the differential is $\\frac{\\partial C}{\\partial a_j^L} = - \\frac{y_j}{a_j^L} + \\frac{1 - y_j}{1 - a_j^L}$.\n",
    "\n",
    "We could compute it like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cost_derivative(self, output_activations, y):\n",
    "    \"\"\"Return the vector of partial derivatives \\partial C_x /\n",
    "    \\partial a for the output activations.\"\"\"\n",
    "    return (1 - y) / (1 - output_activations) - y / output_activations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(even though `output_activations` and `y` are vectors, numpy understands correctly `1 -` and `/`!)\n",
    "\n",
    "We are then going to multiply all this by $\\sigma'(z^L)$ to get $\\delta^L$.\n",
    "\n",
    "However, we know that for the cross-entropy cost function and sigmoid neurons, $\\delta^L = a^L - y$.\n",
    "\n",
    "Keeping the `cost_derivative` method, there would be two issues:\n",
    "\n",
    "* the computation would be suboptimal (simply computing $a^L - y$ is much faster)\n",
    "* we might run into problems with values of $a$ very close to 0 or very close to 1:\n",
    "\n",
    "```\n",
    ">>> import numpy as np\n",
    ">>> 1 / np.array([1e-308])\n",
    "array([1.e+308])\n",
    ">>> 1 / np.array([1e-309])\n",
    "array([inf])\n",
    "```\n",
    "\n",
    "When can a neuron can have an activation lower than $10^{-309}$? Let's invert the sigmoid function:\n",
    "\n",
    "$$\\sigma(x) = \\frac{1}{1 + e^{-x}} \\iff x = - \\ln \\left( \\frac{1}{\\sigma(x)} - 1 \\right)$$\n",
    "\n",
    "This will make the `cost_derivative` method fail as soon as a weighted input is lower than -711.5 (or higher than 711.5, due to the symmetry of the sigmoid function). Such weighted inputs seem unlikely but not implausible in huge networks.\n",
    "\n",
    "In `network2.py`, we solve these two problems by directly using the formula $\\delta^L = a^L - y$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CrossEntropyCost(object):\n",
    "\n",
    "    @staticmethod\n",
    "    def fn(a, y):\n",
    "        return np.sum(np.nan_to_num(-y*np.log(a)-(1-y)*np.log(1-a)))\n",
    "\n",
    "    @staticmethod\n",
    "    def delta(z, a, y):\n",
    "        return (a-y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to choose a neural network's hyper-parameters?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 12 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problem_831601)): implement early stopping using a no-improvements-in-$n$-epochs strategy\n",
    "\n",
    "The code is in the `chap3p12` directory, specifically in the file `network2_es.py` (for *early stopping*).\n",
    "\n",
    "All changes are in the `SGD` method (and its subsequent call in `exec_es.py`).\n",
    "\n",
    "The major change is the replacement of:\n",
    "\n",
    "```\n",
    "for j in range(epochs):\n",
    "```\n",
    "\n",
    "With:\n",
    "\n",
    "```\n",
    "while (len(evaluation_accuracy) <= es or\n",
    "       max(evaluation_accuracy[-es:]) > evaluation_accuracy[-es - 1]):\n",
    "```\n",
    "\n",
    "Executing `exec_es.py` with the parameter `es=5`, we get something like this:\n",
    "\n",
    "```\n",
    "Epoch 0 training complete\n",
    "Accuracy on evaluation data: 9452 / 10000\n",
    "...\n",
    "Epoch 11 training complete\n",
    "Accuracy on evaluation data: 9582 / 10000\n",
    "Epoch 12 training complete\n",
    "Accuracy on evaluation data: 9619 / 10000\n",
    "Epoch 13 training complete\n",
    "Accuracy on evaluation data: 9527 / 10000\n",
    "Epoch 14 training complete\n",
    "Accuracy on evaluation data: 9612 / 10000\n",
    "Epoch 15 training complete\n",
    "Accuracy on evaluation data: 9599 / 10000\n",
    "Epoch 16 training complete\n",
    "Accuracy on evaluation data: 9615 / 10000\n",
    "Epoch 17 training complete\n",
    "Accuracy on evaluation data: 9547 / 10000\n",
    "```\n",
    "\n",
    "Which is what we expected."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 13: a rule for early stopping other than no-improvement-in-$n$\n",
    "\n",
    "No-improvement-in-$n$-epochs looks at the maximum classification accuracy obtained in the $n$ last epochs, and compares it with the $n+1$th latest epoch.\n",
    "\n",
    "We could think about using the average classification accuracy over the last $n$ epochs. We would then stop when the average accuracy over the last $n$ epochs is not greater than the one over the $n$ previous ones. This might prevent an exceptionnally good epoch early on to stop us too early.\n",
    "\n",
    "This is implemented in `chap3p13/network2_es_avg.py`. I've only replaced\n",
    "\n",
    "```\n",
    "while (len(evaluation_accuracy) <= es or\n",
    "       max(evaluation_accuracy[-es:]) > evaluation_accuracy[-es - 1]):\n",
    "```\n",
    "\n",
    "With:\n",
    "\n",
    "```\n",
    "while (len(evaluation_accuracy) <= 2 * es or\n",
    "            sum(evaluation_accuracy[-es:]) >\n",
    "            sum(evaluation_accuracy[-2*es:-es])):\n",
    "```\n",
    "\n",
    "Let's compare 3 runs of both approaches to early stopping:\n",
    "\n",
    "**No-improvement-in-10**\n",
    "\n",
    "<table style=\"border: 1px solid black; margin:auto;\">\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <th style=\"border: 1px solid black\"></th>\n",
    "          <th style=\"border: 1px solid black\">Number of epochs</th>\n",
    "          <th style=\"border: 1px solid black\">Best classification accuracy</th>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Run 1</td>\n",
    "          <td style=\"border: 1px solid black\">17</td>\n",
    "          <td style=\"border: 1px solid black\">96.03</td>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Run 2</td>\n",
    "          <td style=\"border: 1px solid black\">33</td>\n",
    "          <td style=\"border: 1px solid black\">96.50</td>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Run 3</td>\n",
    "          <td style=\"border: 1px solid black\">24</td>\n",
    "          <td style=\"border: 1px solid black\">96.18</td>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Average</td>\n",
    "          <td style=\"border: 1px solid black\">24.7</td>\n",
    "          <td style=\"border: 1px solid black\">96.24</td>\n",
    "        </tr>\n",
    "</table>\n",
    "\n",
    "**No-improvement-in-10-average**\n",
    "\n",
    "<table style=\"border: 1px solid black; margin:auto;\">\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <th style=\"border: 1px solid black\"></th>\n",
    "          <th style=\"border: 1px solid black\">Number of epochs</th>\n",
    "          <th style=\"border: 1px solid black\">Best classification accuracy</th>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Run 1</td>\n",
    "          <td style=\"border: 1px solid black\">39</td>\n",
    "          <td style=\"border: 1px solid black\">96.53</td>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Run 2</td>\n",
    "          <td style=\"border: 1px solid black\">26</td>\n",
    "          <td style=\"border: 1px solid black\">96.43</td>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Run 3</td>\n",
    "          <td style=\"border: 1px solid black\">32</td>\n",
    "          <td style=\"border: 1px solid black\">96.36</td>\n",
    "        </tr>\n",
    "        <tr style=\"border: 1px solid black\">\n",
    "          <td style=\"border: 1px solid black\">Average</td>\n",
    "          <td style=\"border: 1px solid black\">32.3</td>\n",
    "          <td style=\"border: 1px solid black\">96.44</td>\n",
    "        </tr>\n",
    "</table>\n",
    "\n",
    "The average rule seems to yield slightly longer runs and slightly better classification accuracies."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 9 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_336628)): implement a learning rate schedule\n",
    "\n",
    "The code is in `chap3ex9/network2_ls.py` (for *learning schedule*).\n",
    "\n",
    "Executing `exec_ls.py` gives us the following output:\n",
    "\n",
    "```\n",
    "Epoch 0 training complete\n",
    "Accuracy on evaluation data: 9406 / 10000\n",
    "...\n",
    "Epoch 26 training complete\n",
    "Accuracy on evaluation data: 9650 / 10000\n",
    "Epoch 27 training complete\n",
    "Accuracy on evaluation data: 9619 / 10000\n",
    "Epoch 28 training complete\n",
    "Accuracy on evaluation data: 9611 / 10000\n",
    "Epoch 29 training complete\n",
    "Accuracy on evaluation data: 9603 / 10000\n",
    "Epoch 30 training complete\n",
    "Accuracy on evaluation data: 9631 / 10000\n",
    "Epoch 31 training complete\n",
    "Accuracy on evaluation data: 9609 / 10000\n",
    "Epoch 32 training complete\n",
    "Accuracy on evaluation data: 9590 / 10000\n",
    "Epoch 33 training complete\n",
    "Accuracy on evaluation data: 9595 / 10000\n",
    "Epoch 34 training complete\n",
    "Accuracy on evaluation data: 9620 / 10000\n",
    "Epoch 35 training complete\n",
    "Accuracy on evaluation data: 9595 / 10000\n",
    "Epoch 36 training complete\n",
    "Accuracy on evaluation data: 9637 / 10000\n",
    "eta0/1 -> eta0/2\n",
    "Epoch 37 training complete\n",
    "Accuracy on evaluation data: 9671 / 10000\n",
    "...\n",
    "Epoch 56 training complete\n",
    "Accuracy on evaluation data: 9673 / 10000\n",
    "eta0/2 -> eta0/4\n",
    "Epoch 57 training complete\n",
    "Accuracy on evaluation data: 9672 / 10000\n",
    "eta0/4 -> eta0/8\n",
    "Epoch 58 training complete\n",
    "Accuracy on evaluation data: 9709 / 10000\n",
    "...\n",
    "Epoch 68 training complete\n",
    "Accuracy on evaluation data: 9700 / 10000\n",
    "eta0/8 -> eta0/16\n",
    "Epoch 69 training complete\n",
    "Accuracy on evaluation data: 9702 / 10000\n",
    "eta0/16 -> eta0/32\n",
    "Epoch 70 training complete\n",
    "Accuracy on evaluation data: 9705 / 10000\n",
    "eta0/32 -> eta0/64\n",
    "Epoch 71 training complete\n",
    "Accuracy on evaluation data: 9704 / 10000\n",
    "eta0/64 -> eta0/128\n",
    "Epoch 72 training complete\n",
    "Accuracy on evaluation data: 9701 / 10000\n",
    "```\n",
    "\n",
    "The first few halvings result in an immediate boost to the classification accuracy. More importantly, we've reached a classification accuracy of 97.09 percent at epoch 58, which is by far the best result we've obtained in this chapter!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 10 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_281746)): obstacles to the determination of hyper-parameters $\\lambda$ and $\\eta$ using gradient descent\n",
    "\n",
    "The cost function is:\n",
    "\n",
    "$$C = C_0 + \\frac{\\lambda}{2n} \\sum\\limits_w w^2$$\n",
    "\n",
    "where $n$ is the length of the training data, and\n",
    "\n",
    "\\begin{eqnarray}\n",
    "  C_0 = \\left\\{ \n",
    "    \\begin{array}{ll} \n",
    "      \\frac{1}{2n} \\sum_x \\|y-a^L\\|^2 & \\mbox{for the quadratic cost} \\\\\n",
    "      -\\frac{1}{n} \\sum_x \\sum_j \\left[ y_j \\ln a^L_j+(1-y_j) \\ln\n",
    "(1-a^L_j)\\right] & \\mbox{for the cross-entropy cost}\n",
    "    \\end{array}\n",
    "  \\right.\n",
    "\\end{eqnarray}\n",
    "\n",
    "First, we see that $C$ doesn't depend on $\\eta$ at all. That's an obstacle to using standard gradient descent to determine $\\eta$!\n",
    "\n",
    "As for $\\lambda$, we see that the lower it is, the lower the cost function. So if we wanted to minimize C by changing $\\lambda$, it would decrease until reaching 0, which is not what we want."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other techniques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variations on stochastic gradient descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 11 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_603875)): what could go wrong with $\\mu > 1$ or $\\mu < 0$?\n",
    "\n",
    "* If we used $\\mu > 1$ (corresponding to negative friction, or a friction force that accompanies motion instead of opposing it), we could build up (exponential) momentum even if the gradient $\\nabla C$ has always been 0. Or more realistically, once we get to a high value for a velocity $v$, being multiplied by something greater than 1 at every step would make it quite uncontrollable and likely to overshoot the minimum.\n",
    "\n",
    "* If we used $\\mu < 0$, suppose that $\\eta \\nabla C$ is small before $\\mu v$. Then $v$ would oscillate between (potentially large, especially if $\\mu < -1$) positive and negative values, a behavior that doesn't have any reason to be desirable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 14 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#problem_713937)): implement momentum-based stochastic gradient descent\n",
    "\n",
    "See the `chap3p14` directory. In `network2_momentum.py`, the main change is in the `update_mini_batch` method:\n",
    "\n",
    "```\n",
    "self.weights = [(1-eta*(lmbda/n))*w-(eta/len(mini_batch))*nw\n",
    "                for w, nw in zip(self.weights, nabla_w)]\n",
    "self.biases = [b-(eta/len(mini_batch))*nb\n",
    "               for b, nb in zip(self.biases, nabla_b)]\n",
    "```\n",
    "\n",
    "has been replaced with\n",
    "\n",
    "```\n",
    "self.weight_velocities = [mu * v - (eta / len(mini_batch)) * nw\n",
    "                for v, nw in zip(self.weight_velocities, nabla_w)]\n",
    "self.bias_velocities = [mu * v - (eta / len(mini_batch)) * nb\n",
    "                for v, nb in zip(self.bias_velocities, nabla_b)]\n",
    "\n",
    "self.weights = [w + v for w, v in zip(self.weights, self.weight_velocities)]\n",
    "self.biases = [b + v for b, v in zip(self.biases, self.bias_velocities)]\n",
    "```\n",
    "\n",
    "Let's execute `exec_momentum.py` with parameter `mu=0.5`:\n",
    "\n",
    "```\n",
    "Epoch 0 training complete\n",
    "Accuracy on evaluation data: 9438 / 10000\n",
    "Epoch 1 training complete\n",
    "Accuracy on evaluation data: 9500 / 10000\n",
    "Epoch 2 training complete\n",
    "Accuracy on evaluation data: 9566 / 10000\n",
    "...\n",
    "Epoch 27 training complete\n",
    "Accuracy on evaluation data: 9589 / 10000\n",
    "Epoch 28 training complete\n",
    "Accuracy on evaluation data: 9583 / 10000\n",
    "Epoch 29 training complete\n",
    "Accuracy on evaluation data: 9584 / 10000\n",
    "```\n",
    "\n",
    "The best classification accuracy arises at epoch 17, at 95.92 percent. This is worse than what we had without the momentum-based gradient descent (96.39 percent, in Problem 10 above).\n",
    "\n",
    "Let's try with `mu=0.1`:\n",
    "\n",
    "```\n",
    "Epoch 0 training complete\n",
    "Accuracy on evaluation data: 9395 / 10000\n",
    "Epoch 1 training complete\n",
    "Accuracy on evaluation data: 9497 / 10000\n",
    "Epoch 2 training complete\n",
    "Accuracy on evaluation data: 9507 / 10000\n",
    "...\n",
    "Epoch 27 training complete\n",
    "Accuracy on evaluation data: 9614 / 10000\n",
    "Epoch 28 training complete\n",
    "Accuracy on evaluation data: 9594 / 10000\n",
    "Epoch 29 training complete\n",
    "Accuracy on evaluation data: 9606 / 10000\n",
    "```\n",
    "\n",
    "The best classification accuracy arises at epoch 22, at 96.19 percent. Already better, but still worse than before.\n",
    "\n",
    "What about `mu=0.01`?\n",
    "\n",
    "```\n",
    "Epoch 0 training complete\n",
    "Accuracy on evaluation data: 9494 / 10000\n",
    "Epoch 1 training complete\n",
    "Accuracy on evaluation data: 9535 / 10000\n",
    "Epoch 2 training complete\n",
    "Accuracy on evaluation data: 9488 / 10000\n",
    "...\n",
    "Epoch 27 training complete\n",
    "Accuracy on evaluation data: 9596 / 10000\n",
    "Epoch 28 training complete\n",
    "Accuracy on evaluation data: 9582 / 10000\n",
    "Epoch 29 training complete\n",
    "Accuracy on evaluation data: 9603 / 10000\n",
    "```\n",
    "\n",
    "The best classification accuracy arises at epoch 14, at 96.37 percent. Better again, but not too conclusive either."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other models of artificial neuron"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 12 ([link](http://neuralnetworksanddeeplearning.com/chap3.html#exercise_274471)): show that $\\sigma(z) = \\frac{1+\\tanh(z/2)}{2}$\n",
    "\n",
    "By definition,\n",
    "\n",
    "$$ \\tanh(x) = \\frac{e^x - e^{-x}}{e^x + e^{-x}} = \\frac{e^{2x} - 1}{e^{2x} + 1}$$\n",
    "\n",
    "So\n",
    "\n",
    "\\begin{equation*}\n",
    "    \\begin{aligned}\n",
    "        \\frac{1+\\tanh(z/2)}{2} &= \\frac 1 2 \\left( \\frac{e^z + 1 + e^z - 1}{e^z + 1} \\right) \\\\\n",
    "        &= \\frac{e^z}{e^z + 1} \\\\\n",
    "        &= \\frac{1}{1 + e^{-z}} \\\\\n",
    "        &= \\sigma(z)\n",
    "    \\end{aligned}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## On stories in neural networks"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}